package com.codebuffer.nowcoder;

import java.util.Stack;

public class TreeNodeSerializeDeserialize {
    static String Serialize1(TreeNode root) {
        if (root == null) {
            return "#";
        } else {
            return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);
        }
    }
    static String Serialize(TreeNode root) {
        if (null == root){
            return "";
        }
        StringBuilder str = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while(stack.size()>0||null!=treeNode){
            if(treeNode!=null){
                stack.add(treeNode);
                str.append(treeNode.val+"!");
                treeNode = treeNode.left;
            }else {
                str.append("#");
                treeNode = stack.pop().right;
            }
        }
        str.append("#");
        return str.toString();
    }
    static TreeNode Deserialize(String str) {
        if(str.length()==0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tn = new TreeNode(0);
        TreeNode root = tn;
        int left = 1;
        while (str.length()>0){
            int i = str.indexOf("!");
            int j = str.indexOf("#");
            int k = str.indexOf("##");
            if(str.length()==0||"#".equals(str)||"##".equals(str)){
                break;
            }
            if(k==0){
                str = str.substring(k+2);
                stack.pop();
                root = stack.pop();
                left = 0;
            }else if(j==0){
                String val = str.substring(j+1,i);
                str = str.substring(i+1);
                root = stack.pop();
                TreeNode treeNode = new TreeNode(Integer.parseInt(val));
                stack.push(treeNode);
                root.right = treeNode;
                root = treeNode;
                left = 0;
            }else {
                String val = str.substring(0,i);
                str = str.substring(i+1);
                TreeNode treeNode = new TreeNode(Integer.parseInt(val));
                stack.push(treeNode);
                if(left==1){
                    root.left = treeNode;
                }else {
                    root.right = treeNode;
                    left = 1;
                }
                root = treeNode;
            }

        }
        return  tn.left;

    }
//也可以用递归实现
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        treeNode1.left= treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.right = treeNode4;
        String serialize = Serialize(treeNode1);
        TreeNode deserialize = Deserialize(serialize);
        System.out.println();
    }



}
